#include "heapsort.h"

// 构造函数：初始化堆排序状态
// values 为待排序数组，order 指定排序方向（升序或降序）
HeapSort::HeapSort(const QVector<int> &values, SortOrder order)
    : heapSize(values.size()), phase(0), current(values.size() / 2 - 1),
      compareCount(0), swapCount(0), sortOrder(order) {
    // 将初始数据包装为 SortBar 并设为默认颜色
    for (int v : values)
        bars.append({v, Qt::lightGray});
}

// 执行堆排序的一个步骤（构建堆或交换堆顶元素）
void HeapSort::step() {
    // 堆中只剩一个元素，排序完成
    if (heapSize <= 1) return;

    // 每一步前清空颜色标记
    for (auto &bar : bars)
        bar.color = Qt::lightGray;

    // phase == 0：构建最大堆或最小堆
    if (phase == 0) {
        // 所有节点都已堆化，切换到 phase 1
        if (current < 0) {
            phase = 1;
            current = heapSize - 1;
        } else {
            // 从最后一个非叶子节点向上堆化
            heapify(heapSize, current--);
        }
    }
    // phase == 1：堆排序过程
    else if (phase == 1) {
        // 将堆顶元素（最大或最小）与末尾交换
        std::swap(bars[0], bars[--heapSize]);
        swapCount++;
        // 对剩余堆进行堆化
        heapify(heapSize, 0);
    }
}

// 堆调整函数：调整以 i 为根节点、大小为 n 的堆
void HeapSort::heapify(int n, int i) {
    int largest = i;          // 当前根节点
    int l = 2 * i + 1;        // 左子节点
    int r = 2 * i + 2;        // 右子节点

    // 比较左子节点
    if (l < n) {
        bars[l].color = Qt::red;
        compareCount++;
        if ((sortOrder == SortOrder::Ascending && bars[l].value > bars[largest].value) ||
            (sortOrder == SortOrder::Descending && bars[l].value < bars[largest].value)) {
            largest = l;
        }
    }

    // 比较右子节点
    if (r < n) {
        bars[r].color = Qt::red;
        compareCount++;
        if ((sortOrder == SortOrder::Ascending && bars[r].value > bars[largest].value) ||
            (sortOrder == SortOrder::Descending && bars[r].value < bars[largest].value)) {
            largest = r;
        }
    }

    // 若左右子节点中有比当前根更优的，进行交换并递归堆化
    if (largest != i) {
        std::swap(bars[i], bars[largest]);
        swapCount++;
        heapify(n, largest);
    }
}

// 判断是否排序完成（堆中剩一个元素）
bool HeapSort::isFinished() const {
    return heapSize <= 1;
}

// 返回当前可视化数据
const QVector<SortBar>& HeapSort::getData() const {
    return bars;
}

// 获取并清除当前比较次数
int HeapSort::getAndResetCompareCount() {
    int c = compareCount;
    compareCount = 0;
    return c;
}

// 获取并清除当前交换次数
int HeapSort::getAndResetSwapCount() {
    int s = swapCount;
    swapCount = 0;
    return s;
}

// 返回算法的复杂度描述
QString HeapSort::getComplexityInfo() const {
    return "平均 O(n log n)，最好 O(n log n)，最坏 O(n log n)，空间复杂度 O(1)";
}

// 设置排序方向
void HeapSort::setOrder(SortOrder order) {
    sortOrder = order;
}
